package chapter21;

import java.util.*;

/**
 * 用于不相交的数据结构-森林
 */
public class Connection {

    public static List<List<Graph.Node>> connected(Graph G) {
        List<List<Graph.Node>> edge = new ArrayList<>();
        for (Graph.Node v : G.V) {
            markSet(edge, v);
        }
//        Graph.Node start = G.V.get(0);
        for (Graph.Node start: G.V){
            Queue<Graph.Node> queue = new ArrayDeque<>();
            queue.add(start);
            while (!queue.isEmpty()) {
                Graph.Node u = G.table[queue.poll().key];
                Graph.Node next = u;
                while (next != null) {
                    Graph.Node v = G.table[next.key];
                    if (!v.visit) {
                        List<Graph.Node> x = findSet(edge, u);
                        List<Graph.Node> y = findSet(edge, v);
                        if (x != y) {
                            union(edge, x, y);
                        }
                        v.visit = true;
                        queue.add(v);
                    }
                    next = next.next;
                }
                u.visit = true;
            }
        }

        return edge;
    }


    public static boolean same(List<List<Graph.Node>> edge, Graph.Node x, Graph.Node y) {
        return findSet(edge, x) == findSet(edge, y);
    }

    public static void markSet(List<List<Graph.Node>> edge, Graph.Node x) {
        List<Graph.Node> list = new ArrayList<>();
        list.add(x);
        edge.add(list);
    }

    public static List<Graph.Node> findSet(List<List<Graph.Node>> edge, Graph.Node x) {
        for (List<Graph.Node> e : edge) {
//            if (e.size() == 1 && e.get(0).equals(x)) {
//                return e;
//            }
            if (e.contains(x)) {
                return e;
            }
        }
        return null;
    }

    public static void union(List<List<Graph.Node>> edge, List<Graph.Node> x, List<Graph.Node> y) {
        List<Graph.Node> unionList = new ArrayList<>();
        unionList.addAll(x);
        unionList.addAll(y);
        edge.remove(x);
        edge.remove(y);
        edge.add(unionList);
    }

    public static class Graph {

        public List<Node> V;
        public Node[] table;

        public static class Node {
            public String desc;
            public int key;
            public Node next;
            public boolean visit;

            public Node(String desc, int key) {
                this.desc = desc;
                this.key = key;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Node node = (Node) o;
                return Objects.equals(key, node.key);
            }

            @Override
            public int hashCode() {
                return Objects.hash(key);
            }

            @Override
            public String toString() {
                return desc;
            }
        }
    }
}
